1. Field of the Invention
This invention pertains generally to image compression, and more particularly to run-length entropy coding using over-complete dictionaries.
2. Description of Related Art
In a world which increasingly depends on multimedia communications, the ability to further compress image data while retaining image accuracy is highly sought after. The process of image compression is the application of data compression methods to digital images, toward encoding information using fewer data bits than required by an unencoded representation.
As with any communication, there is no benefit to be gained unless both the sender and receiver of the information understand the encoding scheme. Thereby, compressed data can only be understood if the decoding method is known by the receiver.
Compression is beneficial as it helps reduce the consumption of expensive resources, including hard disk space or transmission bandwidth. On the downside, compressed data must be decompressed to be used, and this extra processing may be detrimental to some applications. For instance, a compression scheme for video may require expensive hardware for the video to be decompressed at a sufficiently fast rate to allow viewing in real time as it is being decompressed. Data compression techniques often require trade-offs among various factors, including the degree of compression, the amount of distortion introduced in lossy compression schemes, and the computational resources required to compress and uncompress the data.
Entropy coding is a special form of lossless data compression which typically involves arranging image components in a “zigzag” order employing a run-length encoding (RLE) algorithm that groups similar frequencies together, inserting length coding zeros, and then using Huffman coding, arithmetic coding, or similar on the remaining coefficients.
Run Length Encoding (RLE) is a lossless encoding mechanism which is useful for reducing the size of a binary data stream containing runs of duplicate values, in particular for reducing the bits necessary for encoding a run of zero coefficients. It would be beneficial, however, to be able to perform run-length coding (RLE) with fewer bits than presently required.
Accordingly, a need exists for a system and method of sparse image encoding which can be more efficiently run length encoded. These needs and others are met within the present invention, which overcomes the deficiencies of previously developed encoding systems and methods.